home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / ADJACNCY.C < prev    next >
C/C++ Source or Header  |  1992-01-11  |  21KB  |  523 lines
  1. /*****************************************************************************
  2. *   "Irit" - the 3d polygonal solid modeller.                     *
  3. *                                         *
  4. * Written by:  Gershon Elber                Ver 0.2, Mar. 1990   *
  5. ******************************************************************************
  6. *  Module to handle adjacancies between polygons. Each edge has exactly two  *
  7. * polygons which share it. An edge is implicitly defined by the VList - each *
  8. * VertexStruct defines an edge with its succesor, and has a pointer to the   *
  9. * other polygons using that edge. Those pointers are our target in this      *
  10. * module.                                     *
  11. *****************************************************************************/
  12.  
  13. #include <stdio.h>
  14. #include <math.h>
  15. #include "program.h"
  16. #include "adjacncy.h"
  17. #include "allocate.h"
  18.  
  19. /* #define DEBUG         If the adjacencies should be printed to stdout. */
  20. /* #define DEBUG2     If the hash table content should be printed to stdout. */
  21.  
  22. #define HASH_TABLE_SIZE  100
  23. #define HASH_TABLE_SIZE1 101                 /* One above the above. */
  24. #define HASH_TABLE_SIZE2 50                   /* Half of the above. */
  25.  
  26. typedef struct HashTableEntry {
  27.     int Key;
  28.     PolygonStruct *Pl;
  29.     VertexStruct *V;
  30.     struct HashTableEntry *Pnext;
  31. } HashTableEntry;
  32.  
  33. typedef struct HashTableStruct {
  34.     HashTableEntry *Entry[HASH_TABLE_SIZE1];
  35. } HashTableStruct;
  36.  
  37. /* Prototypes of local function of adjacecies module: */
  38. static void InsertHashTable(HashTableStruct *HashTbl, PolygonStruct *Pl,
  39.                             VertexStruct *V);
  40. static int EdgeKey(VertexStruct *V);
  41. static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl, int EntryNum,
  42.                             HashTableEntry *PHash);
  43. static int SameEdges(PointType V1E1, PointType V2E1,
  44.              PointType V1E2, PointType V2E2);
  45.  
  46. static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
  47.                             HashTableEntry *PHash);
  48. static void SecondEdgeKey(VertexStruct *V, int *Key1, int *Key2);
  49. static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
  50.                     int EntryNum, HashTableEntry *PHash);
  51. static int TestSameDir(PointType Pt11, PointType Pt12,
  52.             PointType Pt21, PointType Pt22);
  53. static void DeleteHashTable(HashTableStruct *SecondHashTable,
  54.                         VertexStruct *V, int EntryNum);
  55.  
  56. /*****************************************************************************
  57. *   Routine to generate adjacencies to the given object. Returns TRUE if all *
  58. * adjacencies were resolved, meaning the object is perfectly closed.         *
  59. *   Note an edge might be only partially adjacent to another edge, and a     *
  60. * second attempt is made to find (again only part of - see below) them. Any  *
  61. * case, FALSE will be returned as there is no way we can say the object is   *
  62. * perfectly closed!                                 *
  63. *   This is the only routine to generate the adjacencies of a geometric      *
  64. * object. These adjacencies are needed for the boolean operations on them.   *
  65. *   Algorithm: for each edge, for each polygon in the object, the edges are  *
  66. * sorted according to the key defined by EdgeKey routine (sort in hash tbl). *
  67. * A second path on the table is made to match common keys edges and set the  *
  68. * pointers from one to another. Note that each edge is common to exactly 2   *
  69. * faces if it is internal, or exactly 1 face if it is on the border (if the  *
  70. * object is open).                                 *
  71. *****************************************************************************/
  72. int GenAdjacencies(ObjectStruct *PObj)
  73. {
  74.     int i, IsOpenObject;
  75.     HashTableStruct *HashTbl, *SecondHashTbl;
  76.     HashTableEntry *PHash, *PHashMatch;
  77.     PolygonStruct *Pl;
  78.     VertexStruct *V;
  79.  
  80.     if (!IS_POLY_OBJ(PObj))
  81.     FatalError("GenAdjacencies: Non polygonal object");
  82.     if (IS_POLYLINE_OBJ(PObj)) return TRUE;     /* No adj. in polyline obj. */
  83.  
  84.     IsOpenObject = FALSE;            /* "Default" is closed object... */
  85.  
  86.     /* Prepare hash tables (for first and second attempts) and clear them.   */
  87.     HashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct),
  88.                                 ALLOC_OTHER);
  89.     for (i = 0; i < HASH_TABLE_SIZE1; i++) HashTbl -> Entry[i] = NULL;
  90.     SecondHashTbl = (HashTableStruct *) MyMalloc(sizeof(HashTableStruct),
  91.                                 ALLOC_OTHER);
  92.     for (i = 0; i < HASH_TABLE_SIZE1; i++) SecondHashTbl -> Entry[i] = NULL;
  93.  
  94.     /* Step one - enter all the edges into the hash table: */
  95.     Pl = PObj -> U.Pl.P;
  96.     while (Pl) {
  97.     V = Pl -> V;
  98.     do {
  99.         InsertHashTable(HashTbl, Pl, V); /* Insert the edge V..V->Pnext. */
  100.         V = V -> Pnext;
  101.     } while (V != NULL && V != Pl -> V);
  102.     Pl = Pl -> Pnext;
  103.     }
  104.  
  105. #ifdef DEBUG2
  106.     printf("Hash Table content:\n");
  107.     for (i = 0; i < HASH_TABLE_SIZE; i++) {
  108.     PHash = HashTbl -> Entry[i];
  109.     if (PHash) printf("\nHashTable entry %d:\n", i);
  110.     while (PHash) {
  111.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  112.         PHash -> V -> Pt[0],
  113.         PHash -> V -> Pt[1],
  114.         PHash -> V -> Pt[2],
  115.         PHash -> V -> Pnext -> Pt[0],
  116.         PHash -> V -> Pnext -> Pt[1],
  117.         PHash -> V -> Pnext -> Pt[2]);
  118.         PHash = PHash -> Pnext;
  119.     }
  120.     }
  121. #endif /* DEBUG2 */
  122.  
  123.     /* Step two - scans all the entries and look for the matching edge.      */
  124.     for (i = 0; i < HASH_TABLE_SIZE; i++)
  125.     while (HashTbl -> Entry[i] != NULL) {
  126.         PHash = HashTbl -> Entry[i]; /* Remove one edge from hash table. */
  127.         HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  128.  
  129.         /* Find matching edge (if perfect match - exactly the same edge) */
  130.         /* Otherwise put the edge in SecondHashTbl.                 */
  131.         if ((PHashMatch = FindMatchEdge(HashTbl, i, PHash)) == NULL) {
  132.         PHash -> V -> PAdj = NULL;
  133.         InsertSecondHashTable(SecondHashTbl, PHash);
  134.         IsOpenObject = TRUE;
  135.         }
  136.         else {
  137. #        ifdef DEBUG
  138.             /* If debug switch the pointers of the edges themselves. */
  139.             PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
  140.             PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
  141. #        else
  142.             /* Otherwise switch pointers of the edges polygons */
  143.             PHash -> V -> PAdj = PHashMatch -> Pl;
  144.             PHashMatch -> V -> PAdj = PHash -> Pl;
  145. #        endif /* DEBUG */
  146.  
  147.         MyFree((char *) PHash, ALLOC_OTHER);
  148.         MyFree((char *) PHashMatch, ALLOC_OTHER);
  149.         }
  150.     }
  151.  
  152. #ifdef DEBUG
  153.     printf("Adjacencies for object %s (found to be open = %d)\n",
  154.     PObj -> Name, IsOpenObject);
  155.     Pl = PObj -> U.Pl.P;
  156.     /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
  157.     while (Pl) {
  158.     V = Pl -> V;
  159.     do {
  160.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  161.         V -> Pt[0], V -> Pt[1], V -> Pt[2],
  162.         V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
  163.         if (V -> PAdj != NULL)
  164.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  165.             ((VertexStruct *) V -> PAdj) -> Pt[0],
  166.             ((VertexStruct *) V -> PAdj) -> Pt[1],
  167.             ((VertexStruct *) V -> PAdj) -> Pt[2],
  168.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
  169.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
  170.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
  171.         else
  172.         printf("No Match!\n\n");
  173.         V = V -> Pnext;
  174.     } while (V != NULL && V != Pl -> V);
  175.     Pl = Pl -> Pnext;
  176.     }
  177. #endif /* DEBUG */
  178.  
  179. #ifdef DEBUG2
  180.     printf("Hash Table content left after all full matches were deleted:\n");
  181.     for (i = 0; i < HASH_TABLE_SIZE; i++) {
  182.     PHash = SecondHashTbl -> Entry[i];
  183.     if (PHash) printf("\nHashTable entry %d:\n", i);
  184.     while (PHash) {
  185.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  186.         PHash -> V -> Pt[0],
  187.         PHash -> V -> Pt[1],
  188.         PHash -> V -> Pt[2],
  189.         PHash -> V -> Pnext -> Pt[0],
  190.         PHash -> V -> Pnext -> Pt[1],
  191.         PHash -> V -> Pnext -> Pt[2]);
  192.         PHash = PHash -> Pnext;
  193.     }
  194.     }
  195. #endif /* DEBUG2 */
  196.  
  197.     /* Time to activate the second attempt - scan SecondHashTable for edges  */
  198.     /* partially adjacent to each other, but with one common vertex!         */
  199.     for (i = 0; i < HASH_TABLE_SIZE; i++)
  200.     while (SecondHashTbl -> Entry[i] != NULL) {
  201.         PHash = SecondHashTbl -> Entry[i];/* Remove one edge from table. */
  202.         SecondHashTbl -> Entry[i] = SecondHashTbl -> Entry[i] -> Pnext;
  203.  
  204.         /* Remove the second instance of this edge with other key: */
  205.         DeleteHashTable(SecondHashTbl, PHash -> V, PHash -> Key);
  206.  
  207.         /* Find matching edge (if perfect match - exactly the same edge) */
  208.         /* Otherwise put the edge in SecondHashTbl.                 */
  209.         if ((PHashMatch = FindSecondMatchEdge(SecondHashTbl, i, PHash)) ==
  210.                                     NULL) {
  211.         PHash -> V -> PAdj = NULL;            /* Failed again! */
  212.         MyFree((char *) PHash, ALLOC_OTHER);
  213.         }
  214.         else {
  215. #        ifdef DEBUG
  216.             /* If debug switch the pointers of the edges themselves. */
  217.             PHash -> V -> PAdj = (PolygonStruct *) PHashMatch -> V;
  218.             PHashMatch -> V -> PAdj = (PolygonStruct *) PHash -> V;
  219. #        else
  220.             /* Otherwise switch pointers of the edges polygons. */
  221.             PHash -> V -> PAdj = PHashMatch -> Pl;
  222.             PHashMatch -> V -> PAdj = PHash -> Pl;
  223. #        endif /* DEBUG */
  224.  
  225.         MyFree((char *) PHash, ALLOC_OTHER);
  226.         MyFree((char *) PHashMatch, ALLOC_OTHER);
  227.         }
  228.     }
  229.  
  230. #ifdef DEBUG
  231.     printf("Adjacencies for object %s - second attempt (found to be open = %d)\n",
  232.     PObj -> Name, IsOpenObject);
  233.     Pl = PObj -> U.Pl.P;
  234.     /* Note that the adjacency in DEBUG is the other edge, not other polygon.*/
  235.     while (Pl) {
  236.     V = Pl -> V;
  237.     do {
  238.         printf("Edge  %10lf %10lf %10lf :: %10lf %10lf %10lf\n",
  239.         V -> Pt[0], V -> Pt[1], V -> Pt[2],
  240.         V -> Pnext -> Pt[0], V -> Pnext -> Pt[1], V -> Pnext -> Pt[2]);
  241.         if (V -> PAdj != NULL)
  242.         printf("Match %10lf %10lf %10lf :: %10lf %10lf %10lf\n\n",
  243.             ((VertexStruct *) V -> PAdj) -> Pt[0],
  244.             ((VertexStruct *) V -> PAdj) -> Pt[1],
  245.             ((VertexStruct *) V -> PAdj) -> Pt[2],
  246.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[0],
  247.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[1],
  248.             ((VertexStruct *) V -> PAdj) -> Pnext -> Pt[2]);
  249.         else
  250.         printf("No Match!\n\n");
  251.         V = V -> Pnext;
  252.     } while (V != NULL && V != Pl -> V);
  253.     Pl = Pl -> Pnext;
  254.     }
  255. #endif /* DEBUG */
  256.  
  257.     MyFree((char *) HashTbl, ALLOC_OTHER);
  258.     MyFree((char *) SecondHashTbl, ALLOC_OTHER);
  259.  
  260.     return !IsOpenObject;
  261. }
  262.  
  263. /*****************************************************************************
  264. * Evaluate a key (integer!) from the given vertex V (in polygon Pl) and      *
  265. * insert that in the hash table:                         *
  266. *****************************************************************************/
  267. static void InsertHashTable(HashTableStruct *HashTbl, PolygonStruct *Pl,
  268.                             VertexStruct *V)
  269. {
  270.     int Key;
  271.     HashTableEntry *PHash;
  272.  
  273.     PHash = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), ALLOC_OTHER);
  274.     PHash -> Pl = Pl;
  275.     PHash -> V = V;
  276.     PHash -> Key = Key = EdgeKey(V);
  277.     PHash -> Pnext = HashTbl -> Entry[Key];
  278.     HashTbl -> Entry[Key] = PHash;
  279. }
  280.  
  281. /*****************************************************************************
  282. *   This routine evaluate a key for the given edge. In order the try to make *
  283. * them unique as possible, the point is projected on a "random" vector. I    *
  284. * picked vector X + 1.57 * Y + 1.29 * Z. If you have better one - change it. *
  285. *   The key itself is the average of the two vertices keys.             *
  286. *   Note we get best results if the object is between ~-10..10.             *
  287. *****************************************************************************/
  288. static int EdgeKey(VertexStruct *V)
  289. {
  290.     int key;
  291.     RealType RKey1, RKey2;
  292.  
  293.     RKey1 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  294.     V = V -> Pnext;
  295.     RKey2 = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  296.  
  297.     key = (((int) ((RKey1 + RKey2) * 10.0)) + HASH_TABLE_SIZE) / 2;
  298.  
  299.     return BOUND(key, 0, HASH_TABLE_SIZE - 1);
  300. }
  301.  
  302. /*****************************************************************************
  303. *   Search The hash table for matching with the given edge pointed by PHash. *
  304. * PHash was extracted from the hash table in entry EntryNum, so the match    *
  305. * is probably in the same entry. If it is not, it must be (if there is one!) *
  306. * in EntryNum+1 as we scans the entries in order and (EntryNum-1) is empty.  *
  307. *   Note that idealy the match was in EntryNum, but because of real number   *
  308. * errors there is a small chance it will be in its neibours: EntryNum +/- 1. *
  309. *****************************************************************************/
  310. static HashTableEntry *FindMatchEdge(HashTableStruct *HashTbl, int EntryNum,
  311.                             HashTableEntry *PHash)
  312. {
  313.     int i;
  314.     HashTableEntry *PLast = NULL, *PMatch;
  315.  
  316.     for (i = EntryNum; i <= EntryNum+1; i++) {
  317.     PMatch = HashTbl -> Entry[i];
  318.     while (PMatch) {
  319.         if (SameEdges(PHash -> V -> Pt,  PHash -> V -> Pnext -> Pt,
  320.               PMatch -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
  321.         /* Delete the matched edge from hash table, and return it: */
  322.         if (PMatch == HashTbl -> Entry[i])
  323.             HashTbl -> Entry[i] = HashTbl -> Entry[i] -> Pnext;
  324.         else
  325.             PLast -> Pnext = PLast -> Pnext -> Pnext;
  326.         return PMatch;
  327.         }
  328.         PLast = PMatch;
  329.         PMatch = PMatch -> Pnext;
  330.     }
  331.     }
  332.  
  333.     return NULL;                  /* No match for this one ! */
  334. }
  335.  
  336. /*****************************************************************************
  337. *   Compere two edges - if the same up to an EPSILON (see APX_EQ, irit.h).   *
  338. * The two vetrices of each edge are given, but no order on them is assumed   *
  339. *****************************************************************************/
  340. static int SameEdges(PointType V1E1, PointType V2E1,
  341.              PointType V1E2, PointType V2E2)
  342. {
  343.     return (PT_EQ(V1E1, V1E2) && PT_EQ(V2E1, V2E2)) ||
  344.        (PT_EQ(V1E1, V2E2) && PT_EQ(V2E1, V1E2));
  345. }
  346.  
  347. /******************************************************************************
  348. *   Everything from this point handle the second attempt - try to match edges *
  349. * which are not complete match - cases which one edge is only part of its     *
  350. * adjacent one. We trap only cases which the two edges has common vertex. If  *
  351. * the two edges has no common vertex (i.e. one is totally in the other) we    *
  352. * still misses that. You are invited to improve that. Any case this one will  *
  353. * have influence in extremely rare cases (The booleans will usually propagate *
  354. * the information using the common vertex edges).                  *
  355. *   Note, the obvious, that if one edge is adjacent to few edges, only one    *
  356. * (arbitrarily) will result in the match, and the other will result as NULL.  *
  357. ******************************************************************************/
  358.  
  359. /*****************************************************************************
  360. * Evaluate two keys (integer!) from the given edge in HashTableEntry struct. *
  361. * This time the keys are of the vertices themselves (see SecondEdgeKet rtn). *
  362. * Note each HashTableEntry hold the key of the other entry this time...      *
  363. *****************************************************************************/
  364. static void InsertSecondHashTable(HashTableStruct *SecondHashTbl,
  365.                             HashTableEntry *PHash)
  366. {
  367.     int Key1, Key2;
  368.     HashTableEntry *PHash2;
  369.  
  370.     SecondEdgeKey(PHash -> V, &Key1, &Key2);
  371.  
  372.     /* And insert the edge as at Key1 (using given HashTableEntry PHash): */
  373.     PHash -> Key = Key2;
  374.     PHash -> Pnext = SecondHashTbl -> Entry[Key1];
  375.     SecondHashTbl -> Entry[Key1] = PHash;
  376.  
  377.     /* And insert the edge as at Key2 (allocating new HashTableEntry for it):*/
  378.     PHash2 = (HashTableEntry *) MyMalloc(sizeof(HashTableEntry), ALLOC_OTHER);
  379.     PHash2 -> Pl = PHash -> Pl;
  380.     PHash2 -> V = PHash -> V;
  381.     PHash2 -> Key = Key1;
  382.     PHash2 -> Pnext = SecondHashTbl -> Entry[Key2];
  383.     SecondHashTbl -> Entry[Key2] = PHash2;
  384. }
  385.  
  386. /*****************************************************************************
  387. *   This routine evaluate two keys for the given edge - one for each of its  *
  388. * vertices, and again tries to make the unique as passible:             *
  389. * picked the same vector: X + 1.57 * Y + 1.29 * Z.                 *
  390. *   Note we get best results if the object is between ~-10..10.             *
  391. *****************************************************************************/
  392. static void SecondEdgeKey(VertexStruct *V, int *Key1, int *Key2)
  393. {
  394.     RealType RKey;
  395.  
  396.     RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  397.     *Key1 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  398.     *Key1 = BOUND(*Key1, 0, HASH_TABLE_SIZE - 1);
  399.  
  400.     V = V -> Pnext;
  401.     RKey = (V -> Pt[0] + 1.57 * V -> Pt[1] + 1.29 * V -> Pt[2]);
  402.     *Key2 = ((int) (RKey * 10.0) + HASH_TABLE_SIZE) / 2;
  403.     *Key2 = BOUND(*Key2, 0, HASH_TABLE_SIZE - 1);
  404. }
  405.  
  406. /*****************************************************************************
  407. *   Search The hash table for matching with the given edge pointed by PHash, *
  408. * as in the second attempt: the keys used here are of the vertices         *
  409. * themselves, so we should search for match in given index EntryNum only.    *
  410. * We search for same vertex AND same direction, which if both match, confirm *
  411. * at list partial adjacency between the two edges (both with same vertex as  *
  412. * one end - the vertex with this key).                         *
  413. *****************************************************************************/
  414. static HashTableEntry *FindSecondMatchEdge(HashTableStruct *SecondHashTbl,
  415.                     int EntryNum, HashTableEntry *PHash)
  416. {
  417.     int EqualFirst, SameDir = FALSE;
  418.     HashTableEntry *PLast = NULL, *PMatch;
  419.  
  420.     PMatch = SecondHashTbl -> Entry[EntryNum]; /* It must be here if exists. */
  421.     while (PMatch) {
  422.     if ((EqualFirst = PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pt)) != 0
  423.               || PT_EQ(PHash -> V -> Pt, PMatch -> V -> Pnext -> Pt)) {
  424.         /* Found same vertex in PMatch as first vertex in PHash - test   */
  425.         /* the direction vectors, to be same also:                 */
  426.         if (EqualFirst) {
  427.         SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
  428.                       PHash -> V -> Pt,
  429.                       PMatch -> V -> Pnext -> Pt,
  430.                       PMatch -> V -> Pt);
  431.         }
  432.         else {
  433.         SameDir = TestSameDir(PHash -> V -> Pnext -> Pt,
  434.                       PHash -> V -> Pt,
  435.                       PMatch -> V -> Pt,
  436.                       PMatch -> V -> Pnext -> Pt);
  437.         }
  438.     }
  439.     else if ((EqualFirst = PT_EQ(PHash -> V -> Pnext -> Pt,
  440.                          PMatch -> V -> Pt)) != 0 ||
  441.         PT_EQ(PHash -> V -> Pnext -> Pt, PMatch -> V -> Pnext -> Pt)) {
  442.         /* Found same vertex in PMatch as second vertex in PHash - test  */
  443.         /* the direction vectors, to be same also:                 */
  444.         if (EqualFirst) {
  445.         SameDir = TestSameDir(PHash -> V -> Pt,
  446.                       PHash -> V -> Pnext -> Pt,
  447.                       PMatch -> V -> Pnext -> Pt,
  448.                       PMatch -> V -> Pt);
  449.         }
  450.         else {
  451.         SameDir = TestSameDir(PHash -> V -> Pt,
  452.                       PHash -> V -> Pnext -> Pt,
  453.                       PMatch -> V -> Pt,
  454.                       PMatch -> V -> Pnext -> Pt);
  455.         }
  456.     }
  457.  
  458.     if (SameDir) {           /* TRUE iff same vertex AND same direction!!! */
  459.         /* Delete the matched edge from the hash table, its compliment   */
  460.         /* with the second key and return a pointer to it:             */
  461.         if (PMatch == SecondHashTbl -> Entry[EntryNum])
  462.         SecondHashTbl -> Entry[EntryNum] =
  463.             SecondHashTbl -> Entry[EntryNum] -> Pnext;
  464.         else
  465.         PLast -> Pnext = PLast -> Pnext -> Pnext;
  466.         /* Uses the key in structure (hold key of other entry!): */
  467.         DeleteHashTable(SecondHashTbl, PMatch -> V, PMatch -> Key);
  468.         return PMatch;
  469.     }
  470.     PLast = PMatch;
  471.     PMatch = PMatch -> Pnext;
  472.     }
  473.  
  474.     return NULL; /* No match for this one ! */
  475. }
  476.  
  477. /*****************************************************************************
  478. *   Test the the two point pairs (defined two edges) are actually on the     *
  479. * same direction - find normalized direction vector for each and test if     *
  480. * their dot product is equal to 1.                         *
  481. *****************************************************************************/
  482. static int TestSameDir(PointType Pt11, PointType Pt12,
  483.             PointType Pt21, PointType Pt22)
  484. {
  485.     PointType Dir1, Dir2;
  486.  
  487.     PT_SUB(Dir1, Pt12, Pt11);
  488.     PT_SUB(Dir2, Pt22, Pt21);
  489.  
  490.     PT_NORMALIZE(Dir1);
  491.     PT_NORMALIZE(Dir2);
  492.  
  493.     return APX_EQ(DOT_PROD(Dir1, Dir2), 1.0);
  494. }
  495.  
  496. /*****************************************************************************
  497. *   Delete entry in SecondHashTable index EntryNum, which holds vertex V.    *
  498. * This vertex MUST be there, otherwise its a fatal error.             *
  499. *****************************************************************************/
  500. static void DeleteHashTable(HashTableStruct *SecondHashTable,
  501.                         VertexStruct *V, int EntryNum)
  502. {
  503.     HashTableEntry *PLast, *PHash = SecondHashTable -> Entry[EntryNum];
  504.  
  505.     while (PHash != NULL) {
  506.     if (PHash -> V == V) break;
  507.     PLast = PHash;
  508.     PHash = PHash -> Pnext;
  509.     }
  510.  
  511.     if (PHash == NULL)
  512.     FatalError("DeleteHashTable: No hash table entry to delete\n");
  513.     else {
  514.     if (PHash == SecondHashTable -> Entry[EntryNum])
  515.         SecondHashTable -> Entry[EntryNum] =
  516.         SecondHashTable -> Entry[EntryNum] -> Pnext;
  517.     else
  518.         PLast -> Pnext = PHash -> Pnext;
  519.     MyFree((char *) PHash, ALLOC_OTHER);
  520.     }
  521. }
  522.  
  523.